package developer.算法.二叉树.二叉树中的最大路径和;

/**
 * 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
 * <p>
 * 路径和 是路径中各节点值的总和。
 * <p>
 * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
 */
public class ErChaShuZhongDeZuiDaLuJingHe {


    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */

    public static void main(String[] args) {

        Solution solution = new Solution();
//        TreeNode treeNode = new TreeNode(1, new TreeNode(2), new TreeNode(3));
        TreeNode treeNode = new TreeNode(2, null, new TreeNode(-1));
        int i = solution.maxPathSum(treeNode);
        System.out.println(i);
    }

    static class Solution {
        int result = Integer.MIN_VALUE;


        public int maxPathSum(TreeNode root) {
            deep(root);
            return result;
        }

        public Integer deep(TreeNode root) {
            if (root == null) return 0;
            int left = Math.max(deep(root.left), 0);//巧妙的避开了边界条件 最边边的节点
            int right = Math.max(deep(root.right), 0);

            int currentVal = root.val + left + right;
            result = Math.max(result, currentVal);


            return Math.max(left, right) + root.val;
        }
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
